昨日の夢

114514

1114143454357917984058790174890

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment

一些符号： 表示从中很有收获的题， 表示差不多会，参考题解做出来的题， 表示完全不会，看题解才会的题， 表示之前改的题。在题解中穿插表示具体部分。

[ARC104C] Fair Elevator (*2009)

考虑有一个区间 ，钦定没有另一个区间 满足 。考虑 位置对应的右端点，一定为 。于是确定了 就可以确定 。

然后可以 dp。设 为 内是否都满足。转移是枚举一个 ， 配对，然后暴力 判断是否合法。细节多。时间复杂度 。

[ARC104D] Multiset Mean (*2251)

朴素 dp 是设 表示当前选完了 内的数，选了 个，和为 的方案数。每次枚举选了几个 ，复杂度为 。

套路地，考虑先钦定一个 ，于是可以省去 这一维，变成 。

然后发现其实有很多重复算的东西。考虑钦定了 之后，把 变成了 。 不用管，乘上随意选 个的 种方案即可。然后要求 和 这两部分取得的数和为 ，也就是求 和 中选出和相同的方案数。

于是设 为已经选完了 ，和为 的方案数。暴力转移是 的，加上前缀和优化多重背包之后 可过。这个前缀和的方法是，设 然后做。

[ARC104E] Random LIS (*2824)

首先期望转 LIS 长度和除以方案数。LIS 这个东西不好刻画，但是发现 ，所以考虑直接枚举每个数排名，也就是枚举 离散化后的序列。

然后考虑知道这个序列之后怎么求方案数。先想一个弱化版的问题：有 个数，已知他们的排名，每个数的取值范围为 ， 为定值。求方案数。答案显然是 。

回到原问题，尝试转化成弱化版问题。注意到值域非常大（）但是 非常小。这启示我们， 要不只有小部分值是有用的，要不可以把一段值放在一起算。这题显然是后者。

考虑把序列 排序后去重得到序列 ，于是发现对于 这个区间，能取到区间内任意一个数的 的集合相同。也就是说，我们如果知道了对于每个 ，哪些 在这个区间中，就可以用弱化版的方法算出每个 的方案数，最后再乘起来即可。

这里再次暴力枚举每个排名所对应的数属于哪个 的 区间即可。时间复杂度远小于 。

[ARC104F] Visibility Sequence (*3213)

对于序列上和某些位置的最小值最大值计数相关的，考虑一些类似笛卡尔树的 dp，更进一步，按照最大值/最小值划分区间后进行区间 dp。设 表示 这个区间内，所有值 的方案数。从类似 转移过来。

此时有一个问题：为什么这样不会算重/漏？首先不会算漏，因为每一步都贪心地取到了最大范围，能算的情况都会算到。并且不会算重， 感性理解，因为从最终状态开始往下推，如果有一个 可行，不会从 转移过来。于是每一种 都对应了唯一一种转移过程。

但是发现 ，不过这是诈骗， 因为发现我们只关心取值大小可能导致的大小关系，所以 可以向 取 ，只用这部分就可以凑出来需要的大小关系。时间复杂度 。

[ARC105C] Camels and Bridge (*1964)

于是直接枚举排列（最近怎么做了 3 道）。考虑如果有两个限制 满足 则限制 是没用的，丢掉。然后形成了 都单调上升的序列。

考虑从前往后依次枚举，确定第 只骆驼的位置时，枚举所有 ，考虑区间内的体重总和，再二分出限制，确定可以放的最左的位置即可。贪心地想，每一个都尽可能往左靠是正确的。时间复杂度 。

[ARC105D] Let’s Play Nim (*1871)

其实就是问能不能把每个数分配到一个集合中使得每个集合中数字和的异或和为 。

考虑构造。如果 为偶数，先手每次选最大的，丢到一起，记选择的序列为 ，后手选的为 ，则 ，又 ，则不管后手怎么选，他选的那一部分 和都 ，取等当且仅当 中的数可以两两配对，每对内相等。能取等后手胜，否则先手。

如果 为奇数，则类似的，先手不管选什么数，后手每次选当前最大加入先手第一次放的那一堆，则一定有这一堆的和大于其它的所有数之和。所以后手必胜。

[ARC105E] Keep Graph Disconnected (*2615)

考虑如果没有第一个条件，则一共有 条边可以加，看这个数的奇偶性即可。

有了第一个条件，注意到最后一定剩下两个集合， 号点在其中一个， 在另一个。设两个集合分别为 ，则根据 的奇偶性即可得出真实胜负。接下来就看双方如何操作可以使得最后奇偶性变成怎么样。

最详细的一集：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

if((n&1)){//总点数为奇数 -> 最后一定剩 01 -> 胜负情况不变
	if(p&1){
		puts("First");
	}else{
		puts("Second");
	}
	return;
}
if(x+y==2){//无法操作 -> 直接算影响
	p-=x==2;
	if(p&1){
		puts("First");
	}else{
		puts("Second");
	}
	return;
}
if(p&1){//原本状态先手必胜
	if((x+y)&1){//可以操作奇数次 -> 最后操作的人是先手 -> 先手希望最后不为 101
		if(!u||!v){//一开始 1,n 中有一个 0 -> 先手可以控制最后 1,n 一定有一个 0 -> 先手胜
			puts("First");
		}else if(!y){//一开始全 1，先手先使 1 或 n 变 0 -> 后手只能把这个变为 1 否则成上面情况 -> 可以保持后手操作完后全 1 -> 先手胜
			puts("First");
		}else{//一开始有 0，后手可以保持操作完后中间有 0，1,n 为 1 -> 后手胜
			puts("Second");
		}
	}else{//可以操作偶数次 -> 最后操作的是后手 -> 后手希望最后不为 000
		if(!u||!v){//一开始 1,n 中有一个 0 -> 先手可以保持操作完后最后 1,n 一定都是 0 -> 先手胜
			puts("First");
		}else{//一开始全 1,n 都为 1，后手可以保持操作完后 1,n 都为 1 -> 后手胜
			puts("Second");
		}
	}
}else{//原本状态后手必胜
	if((x+y)&1){//可以操作奇数次 -> 最后操作的是先手 -> 先手希望最后不为 000
		if(!u&&!v){//一开始 1,n 都为 0，后手可以保持操作完后 1,n 都为 0 -> 后手必胜
			puts("Second");
		}else{//一开始 1,n 中有一个 1，先手可以保持操作完后 1,n 都是 1 -> 先手必胜
			puts("First");
		}
	}else{//可以操作偶数次 -> 最后操作的是后手 -> 后手希望最后不为 101 
		if(!u&&!v){//一开始 1,n 都为 0，后手可以保持操作完后 1,n 都为 0 -> 后手必胜
			puts("Second");
		}else if(!u||!v){//一开始 1,n 有一个 1，先手把其中 0 变 1
			if(y==1){//中间没有 0，后手把 1,n 之一变成 0，保持操作完后中间一直全 1 -> 后手必胜
				puts("Second");
			}else{//中间有 0，先手保持操作完后 1,n 为 1，中间有 0 -> 先手必胜
				puts("First");
			}
		}else{//一开始 1,n 都为 1，先手保持操作完后 1,n 为 1，中间有 0 -> 先手必胜
			puts("First");
		}
	}
}

[ARC105F] Lights Out on Connected Graph (*3231)

二分图，想到黑白染色。于是对于一个点集 ，枚举其染为白的子集 ，则 不要求连通， 的染色方案数就是 。其中 表示 的导出子图的边数。

但是这是不一定联通的情况。考虑如果不限制是二分图，求连通的方案数。这个弱化问题也很难直接做， 于是考虑容斥。对于本题，设 为 是一个连通块，染色的方案数。转移就是减去不为一个连通块的方案数，即 。注意到这样还会算重，于是钦定 就可以了。

在做这题时的主要问题还是太过纠结边的连法。 其实二分图的性质很好，只要对染色方式计数就行了。

[ARC106C] Solutions (*1225)

最简单的一集。发现 A 做法能取到最大值，所以 无解。 用脚构造。 显然无解，其他用脚构造即可。

[ARC106D] Powers (*1988)

先转换成

令 ，则

。

这几个都可以简单预处理，于是做完了。时间复杂度 。

[ARC106E] Medals (*2825)

分配某奖牌， 考虑转化成匹配，即每个人要找到 个可行位置和它匹配。 匹配的可行性问题，想到 Hall 定理，而且数据范围也支持我们枚举集合。

于是二分答案 ，注意到 ，于是暴力枚举每一天有哪些人在，高维前缀和算出和人的集合 有交的位置个数 ，看是否有 即可。时间复杂度 。

[ARC106F] Figures (*2755)

第一次用 GF 推式子。

翻译一下就是这颗树每个点的度数 ，并且要额外乘上 的权值，求所有树的权值之和。

由于是 的限制，所以考虑 prufer 序列。考虑枚举每个点的度数为 ，变成 prufer 序列，则有 。可以背包 dp 解决。

但是 显然不够，不过背包很难优化。 此时想到 GF（但是我一道 GF 都没做过是怎么想到的？？？）。设 为第 个点对应的 GF，则有：

注意到此时 比较不好看，于是我们默认给每个点分配一个度数（事实上这也是必须要的），则限制变成 ，上式变成 。

要求的即为 。

将 转为封闭形式即为 。

则 。

再转回形式幂级数为 。

则 。 解决。

[ARC107C] Shuffle Permutation (*1223)

又是简单的一集。首先行列是相互独立的，如果第 行和第 行可以互换则连一条边，容易发现这样在同一个连通块内的行之间顺序任意，方案数为阶乘。全部乘起来就是答案。

[ARC107D] Number of Multisets (*2099)

考虑将操作放到二叉树森林中。限制就是二叉树一共有 个根， 个叶子，并且没有只有一个儿子的节点。合法的二叉树和可重集形成双射。

自底往上考虑每一层，类似阶梯型 dp，于是就有两种操作：在这一层新增一个点，或者在上面新增一层。第二种操作要求当前层有偶数个节点，随后每两个相邻节点都会并到一个父亲下面。

再考虑两种操作对原问题的影响：第一种显然是使元素数 ，和 。第二种会使全部元素对和的贡献 ，也就是使和 ，并要求和此时为偶数。

于是设 表示前 个数，和为 的方案数。则有 。 解决。

[ARC107E] Mex Mat (*2604)

发现多操作几轮就一定有 。于是暴力做个 轮后算对角线即可。证明不想写了。

[ARC107F] Sum of Abs (*3130)

首先考虑，最优情况下，所有 的和 的之间不连通，答案为 。

但是显然很多时候取不到这个上界， 但是这启示我们将最后选择贡献 的和 的分开，两者之间不能有连边。这相当于分成两个集合，一个是贡献 的，一个是 的。 于是考虑最小割建模。

考虑先令 的贡献 ，否则贡献 。如果 不在原来所属的集合，则会造成 的贡献。如果删掉 点，则会造成 的贡献。如果 间有边且不在一个集合，则造成 的贡献。这样连边即可。

[ARC108C] Keep Graph Connected (*1460)

感觉是更简单的一集。显然拎出来一棵生成树再随便染色就做完了。

[ARC108D] AB (*1987)

考虑推一些性质。一开始序列是 AB，不妨设 ，另一种情况大概是对称的。则序列会变成 AAB。此时发现，右半边仍然是 AB，怎么做都只能再增加一个 A。所以只用考虑左半边的 AA。

同时注意到这要求最终的 。

• 如果 ，那么最终序列就只有 AAA...AB 这一种情况。
• • 否则，若 ，则可以发现，任何一个 的序列都可以构造出来，方法是先不管开头的 A 和结尾的 B ，每次找到最后一个连续段，先把这个连续段的第一个位置填上，再往后填。故方案数为 。
  • 否则还是类似上面的，但是此时不能有两个连续的 B，因为 。这是一个经典计数问题，设 为长为 的序列的方案数，则 为 的斐波那契数列。方案数为 。

的答案是类似的，对称地推一下即可。

[ARC108E] Random IS (*3101)

一个很重要的性质：如果已经确定 被选中，那么 内的期望就和其他位置无关了。于是想到进行一个区间 dp：设 表示已经确定 选中， 区间内的期望长度。转移就是枚举一个 表示 内下一个选的是 ，算所有合法的 和 之和再除以可能数量。

做的时候有一个问题：为什么这样会把先选 再选一个 的情况算上。 事实上此时没有必要关注选数的顺序，只要关注选了什么就行了。于是这样是正确的。

然后发现可以 BIT 简单维护，时间复杂度 解决。

[ARC108F] Paint Tree (*2646)

这题之前自己做出来了，两次/hanx

首先有关键性质：若最大距离的同色点对为 ，树上的任意一条直径 满足 其中至少一个成立。

证明：反证。若有一条直径两端点为 且 不是任何的一个 或 ， 互不相同，钦定 ，则 。同时，因为 为直径，，，于是 ，又 ，则 ，此时显然 同色且距离更远，不成立。

所以先找出任意一条直径 ，有 种情况同色，答案为 。否则，钦定 ，对于每个点 考虑钦定 的时，有多少种情况使得 与一个直径端点的距离是最终答案。

预处理出 然后排序后，处理出此时选这个点做答案的其中一个端点是否可行（）有多少点 是 为 都行（即为排序后排名 ），然后计算即可。最后将这部分贡献 ，因为加上 的情况。

[ARC109C] Large RPS Tournament (*1167)

考虑这个过程是一棵完全二叉树。你对 暴力做就得到了更上一层循环的字符串。这样做 遍就行了。

[ARC109D] く (*2394)

这种题怎么做？完全不会。

[ARC109E] 1D Reversi Builder (*2661)

因为表面是一个博弈，所以先考虑分析两方的最优策略。考虑分析一些性质。

Lemma：黑白棋子构成级极长同色连续段数量不会超过 。

证明显然，如果在某个时刻从 变成了 ，那么一定会将一段覆盖，变成 个极长同色连续段。

然后，对于这种覆盖的问题，一般都是有很多位置没有用，只用考虑一些特殊的位置。对于这题，由于是两个相同位置覆盖中间的，所以尝试着只考虑每种颜色最左/右出现的位置。

容易发现，令 为列表上位置 的颜色，若 ，那么最后全部一定都是 的棋子。证明显然。

否则不妨钦定 。此时我们只用关注最后一个 的位置 和最后一个 的位置 。若 则 ，答案为 。否则手玩发现，若先取到 再取到 ，那么黑方在取到 后可以直接取 ，因为 全黑，所以 不会再变成白色。同时 还没取，取到 后 全黑，也无法变成白色。所以最后黑棋数量为 。

那么策略就很显然了：黑方尽可能往 处靠，白方往 。直接对这个计数也是简单的：枚举起点 ，分成 以及一些特殊情况，分别预处理一些东西然后算。作者也是这么过的。

但是你会发现这太蠢了！除了 之外，的所有情况， 如果将所有黑白翻转，答案就会变成 。若 且 也满足这个性质。此时期望就是 。但是若 ，黑方由于先手，所以一定能抢先取到 。于是期望要加上 。只用简单预处理，统计所有这样的贡献之和即可。

[ARC109F] 1D Kingdom Builder (*3625)

一个非常 educational 的想法： 不从怎么进行操作入手，而是从最终形态入手，再根据可能的最后的形态推出最小操作次数。

考虑最后会形成若干连续段。对于每个连续段，都是先标记其中的一部分，最后再拓展成完整的连续段。

然后对第一步讨论。若填的第一个位置两边颜色不同，则一定要不断扩张直到两边相同，不妨为 。

然后 没有限制，可以填任意多个极长 连续段，最后填一个任意长度 连续段。

此时发现，若还要填 的连续段，那么需要将所有 旁边的极长 连续段填上，不如将上述 交换操作。于是可以填的总共有：一个两边都是 的 ，若干个极长 连续段，一个任意长度 连续段。然后再进行开头说的拓展。

于是可以 dp 了：设 表示当前处理到第 位，两边都是 的 是否使用过，任意长度 连续段是否使用过，当前位置不标记/标记了但是后面组成极长 连续段/是极长 连续段的一部分/选且已经组成了极长 连续段。讨论每一种转移即可。

[ARC110C] Exoswap (*1100)

依次找 往前操作即可。

[ARC110D] Binomial Coefficient is Fun (*2078)

非常有趣的组合意义。看到上指标和要求为 ，联想到范德蒙德卷积，考虑从组合意义入手看有没有很好的算法。

考虑这大概能表示成总共 个位置选 个。但是发现若选的第 个和第 个位置中间有若干空位，则 不是唯一确定的。然后发现可以通过加一个分隔符的方式确定。于是就变成了不超过 个位置选 个的方案数，根据经典上指标求和，答案即为 。 暴力算组合数即可。

[ARC110E] Shorten ABC (*2973)

看到这种两个字符合成一个，最后还要计数的问题， 可以构造一个关于 的简单函数 ，使得不管怎么操作 都不变，然后从这个不变中寻找性质。

对于 AGC027E，这个构造的方法就是令 ，。一开始也想的是模意义下的东西，但是一直没想出来。直到想到异或，瞬间有如醍醐灌顶：令 ，设 ，这样就成功构造出来了一个不变的 了。

于是，此时知道一个区间的异或和，就能知道这个区间可能合成什么字符。但是什么时候可以什么时候不能合成一个字符呢？显然异或和为 和区间长度 且区间内 全相等时不行。

其他情况是否一定可行？感性理解，可以归纳地证明：若一个区间不是上两种情况，一定就能分成两个不是上面两种区间的区间。

然后考虑进行一个最简单的 dp：设 表示 的方案数。求 时，先枚举最后一位是什么。根据对应的异或和，就可以知道可以从哪里转移过来。

此时就会有一个结论：对于一个位置 和一个异或和 ，大部分情况下只会从最大的 满足 转移过来。这是因为 的答案会包含 $1,j’$ 的答案。

证明：设另一个 也满足 。令 能拼出来长为 的串 ，若 和 不全相同，根据上面的结论， 拼上 一定能合成一个和 相同的字符。否则，考虑先将 拼到 后面，再找到从后往前第一个不同的位置记为 ，则反复合并 ，一定也能得到和 相同的串。

为什么说大部分情况下呢？因为如果找不到上述 就会有问题。此时 就是会从这些 转移过来的。但是发现会有这种情况当且仅当 全部相同且 不全部相同。即 是固定的。所以可以找到每一个 并记录下来，后面再从这里转移。

做完了。时间复杂度 。

[ARC110F] Esoswap (*2719)

首先可以发现，对于一个固定位置操作若干次大概是能使这个位置变成任意一个数的。于是有个猜测的做法：倒序枚举 不断对 操作直到 ，然后再操作一次使 。

试了一下发现不太行。因为如果此时 就怎么也动不了了。然后发现 其实非常不好，但是发现，可以通过操作若干次数字 的方式使 循环位移，于是先不断操作 使 固定到 的位置。

这一步似乎也可以通过不断操作位置 做到。

然后考虑依次使 到 再到对应位置。此时又发现一个问题：当 的时候又会出问题。

但是发现这个时候好操作很多：只需要不断操作数字 ，使它去到还没归位的数的末尾。然后变成不断操作 即可。再发生一次就变成不断操作 ，以此类推。

最后再不断操作数字 ，整个 满足要求即可。

[ARC111C] Too Heavy (*1750)

若一个位置一开始就有 则一定无法操作。否则按 从大到小，使 一步到 即可。

[ARC111D] Orientation (*2064)

若 则一定是 ，否则 的 在同一个强连通块内。因为保证有解所以 dfs 一遍即可。

[ARC111E] Simple Math 3 (*2541)

cnm 怎么是类欧，如果这辈子有幸学到类欧了就改这个题。

[ARC111F] Do you like query problems? (*3119)

考虑拆贡献：设第 次操作修改了位置 的值为 ，使其在第 次操作的查询贡献。

不妨令第 操作为 ， 之前最后一次 且 的操作位置为 。则要满足以下条件：

• 内任意。

• 内，所有修改操作要不与 不交，要不是 或 。

• 内，所有修改操作要不与 不交，要不是 或 。

• 内任意。

四种情况分别有的方案数为：

再加上 分别的方案数：

所以答案即为